/*find the key in a sorted sequence a[low]...a[high]
*if the key not found, return the element more than key but closest to
*key or a[high]
*/
int binary_search(int a[], int low, int high, int key){
	int mid, lim=high;
	while(low<=high){
		mid = low +((high-low)>>1);
		if(a[mid]>key) high = mid-1;
		else if(a[mid]<key) low = mid+1;
		else return mid;
	}
	if(low>lim) return low-1;
}
/*key is a element in sorted sequence a[low]...a[high], and may appears sereval times
*this function returns the smallest index such that a[index]==key
*/
int lower(int a[], int low, int high, int key) {
	int mid;
	while(low<high) {
		mid = low+((high-low)>>1);
		if(a[mid] == key &&(!mid||a[mid-1]!=key)) return mid;
		else if(a[mid] == key) high = mid-1;
		else low = mid+1;
	}
	return low;
}
/*return the largest index such that a[index]==key*/
int upper(int a[], int low, int high, int key) {
	int mid;
	while(low<high) {
		mid = low+((high-low)>>1);
		if(a[mid] == key&&(mid==high||a[mid+1]!=key)) return mid;
		else if(a[mid] == key) low = mid+1;
		else high = mid-1;
	}
	return low;
}

/*a[] and b[] are both sorted array.
* if a[] contains the kth smallest element of the mix sequence of a[] and b[]
* then return true and set ret to the element, otherwise return false and the value of
* ret is void
*/
bool sub_kth_smallest(int a[], int m, int b[], int n, int k, int &ret){
	int al = 0, ah = m-1, am;
	int bl = 0, bh = n-1, bm;
	int cnt_l, cnt_u;
	int low_lim, upper_lim;
	while(al<=ah){
		am = al+((ah-al)>>1);
		bm = binary_search(b, bl, bh, a[am]);
		low_lim = lower(b, bl, bm, b[bm]);
		upper_lim = upper(b, bm, bh, b[bm]);

		if(a[am] == b[bm]) {
			cnt_l = low_lim+am+1;
			cnt_u = cnt_l+upper_lim-low_lim+1;
		} else if(a[am]<b[bm]) {
			cnt_l = low_lim+am+1;
			cnt_u = cnt_l;
		} else {
			cnt_l = low_lim+am+2;
			cnt_u = cnt_l;
		}

		if(k<=cnt_u && k>=cnt_l) {
			ret = a[am];
			return true;
		} else if(cnt_u<k) {
			al = am+1;
			bl = bm;
		} else {
			ah = am-1;
			bh = bm;
		}
	}
	return false;
}

/*find the kth smallest element of mix sequence of a[] and b[]*/
int kth_smallest(int a[], int m, int b[], int n, int k){
	int ret;
	if(!sub_kth_smallest(a, m, b, n, k, ret))
		sub_kth_smallest(b, n, a, m, k, ret);
	return ret;
}
